#include "graphsupport/solve/facilitylocation/BinaryRunFacilityLocationSolver.h"

#include <assert.h>
#include <iostream>

#include "accumulsupport/AccumulSupport.h"

Graph::AdjCoefType computeGreedy(
	Graph & graph,
	int firstBipart,
	const std::vector< char > & usedFacilities,
	std::vector< int > & cityWtn
	)
{
	Graph::AdjMatrixType adjMatr = graph.getAdjacentMatrixArr();
	int n = graph.getVertexCount();
	int secondBipart = n - firstBipart;

	Graph::AdjCoefType edgesSum = 0;

	accumf::reinit( cityWtn, firstBipart, -1 );

	for ( int i = 0; i < firstBipart; i++ )
	{
		Graph::AdjCoefType minEdg = graph.getInfEdge();
		int witness = -1;
		for ( int j = firstBipart; j < n; j++ )
		{
			if ( usedFacilities[j - firstBipart] && adjMatr[i][j] < minEdg )
			{
				minEdg = adjMatr[i][j];
				witness = j;
			}
		}
		if ( witness == -1 )
		{
			return graph.getInfEdge();
		}
		cityWtn[i] = witness - firstBipart;
		edgesSum += minEdg;
	}

	return edgesSum;
}

Graph::AdjCoefType computeFacilitiesCost(
	int secondBipart,
	std::vector< char > & isOpen,
	const FacilitiesGraph::FacilityPricesVecType & facilitiesPriceVec
	)
{
	Graph::AdjCoefType fclSum = 0;
	for ( int i = 0; i < secondBipart; i++ )
	{
		if ( isOpen[i] )
		{
			fclSum += facilitiesPriceVec[i];
		}
	}
	return fclSum;
}

bool increaseBinBuf( std::vector< char > & usedFacilities )
{
	int i = usedFacilities.size() - 1;
	while ( i >= 0 && usedFacilities[i] > false )
	{
		usedFacilities[i] = false;
		i--;
	}
	if ( i == -1 )
	{
		return false;
	}
	usedFacilities[i] = true;
	return true;
}

bool BinaryRunFacilityLocationSolver::solve(
	FacilitiesGraph & fgraph,
	std::vector< char > & isFacilityOpenVec,
	std::vector< int > & cityWitnessVec
)
{
	int n = fgraph.getVertexCount();
	int citiesCount = fgraph.getCitiesCount();
	int facilitiesCount = fgraph.getFacilitiesCount();
	Graph::AdjMatrixType adjMatr = fgraph.getAdjacentMatrixArr();

	std::vector< char > usedFacilities( facilitiesCount, 0 );
	std::vector< int > cityWtn( citiesCount, -1 );
	FacilitiesGraph::FacilityPriceType bestSum = fgraph.getInfEdge() * ( citiesCount + facilitiesCount + 1 );

	do
	{
		Graph::AdjCoefType edgesSum = computeGreedy(
			fgraph,
			citiesCount,
			usedFacilities,
			cityWtn
		);
		if ( edgesSum < bestSum )
		{
			Graph::AdjCoefType fclSum = computeFacilitiesCost(
				facilitiesCount,
				usedFacilities,
				fgraph.facilitiesPrices
			);
			Graph::AdjCoefType totalSum = edgesSum + fclSum;
			if ( totalSum < bestSum )
			{
				bestSum = totalSum;
				isFacilityOpenVec = usedFacilities;
				cityWitnessVec = cityWtn;
			}
		}
	} while ( increaseBinBuf( usedFacilities ) );

	return bestSum < fgraph.getInfEdge();
}
